package b_sorting_advance.b_quick_sort;

import org.junit.Test;
import utils.ArrayGeneric;
import utils.sorting_helper.SortingTest;

import java.util.Arrays;

/**
 * @Author: DeLucia
 * @Description: 快速排序号称20世界最重要的算法之一
 * @Date: 2019/1/24 0:48.
 */
@SuppressWarnings("unchecked")
public class QuickSorting extends SortingTest {

    @Override
    public void sort(ArrayGeneric arr) {
        quickSort(arr, 0, arr.length() - 1);
    }

    /**
     * 1- 快速排序
     * 采用分治法的思想
     * 选择数组的第一个元素作为基准p进行分区
     * 分区的结果就是将比基准p小的元素放在左边,比基准p大的元素放在右边,并返回基准p的位置
     * 然后再对基准p两边的区域进行同样的递归分区操作
     * 问题
     * 1. 没有对小规模数组使用插入排序提高性能
     * 2. 基准选取过大和过小时影响效率， 尤其对有序数组排序效率最差， 将退化成N2时间复杂度
     * 3. 递归层次过深容易出现栈溢出
     * @param arr 递归的数据
     * @param l   递归的区域的左下标
     * @param r   递归的区域的左下标
     */
    private void quickSort(ArrayGeneric arr, int l, int r) {
        if (l >= r) { // 递归的终点
            return;
        }

        int p = partitionOnePivotLeft(arr, l, r); // 第一个分区版本 单基准（始终位于最左）可能退化到N2时间复杂度
        quickSort(arr, l, p - 1);
        quickSort(arr, p + 1, r);
    }

    /**
     * 分区操作 - 快速排序的核心
     * 第一个版本：单基准 选取最左位置
     * 存在问题： 最差情况即当数组完全有序的时候，将退化成O(N^2)的时间复杂度，因此基准每次都是被放置在一侧
     *
     * @param arr 分区的数据
     * @param l   分区操作的左坐标
     * @param r   分区操作的有坐标
     * @return 分区后基准所在下标
     * 1.根据第一个元素的值确定分区的基准 arr[l]
     * 2.从第二个元素开始迭代（i = l +1）和基准比较
     * a.如果比基准值小就陆续交换到基准的右面， 同时j++
     * 3.结束条件 i <= r 这时数组是这样的  {基准arr[l] > 比ref小的元素们（→j）  > 不小于ref的元素们(→r)}
     * 4.最后交换当前迭代的元素arr[i]和arr[j+1]，同时
     * 5.这时数组时这样的  { 比ref小的元素们 > 基准arr[j] > 不小于ref的元素们}
     * 6.返回交换后基准arr的新的下标j - 用于返回给递归函数 继续 对 基准的左右两边进行递归分区操作
     */
    private int partitionOnePivotLeft(ArrayGeneric arr, int l, int r) {

        //单元测试
        System.out.print("partition from " +l+ " to " + r +": ");

        Comparable ref = arr.get(l); // 默认将l所在元素当做参考值进行分区

        int j = l;
        // i 代表进行比较操作的下标 从 l + 1开始
        // j 代表比ref小的区域的数组的最后一个元素 初始位置是l 每次发生交换 +1
        // arr[l];arr[l + 1..j] < ref; arr[j+1...i) > ref;
        for (int i = l + 1; i <= r; i++) {
            if (ref.compareTo(arr.get(i)) > 0) {

                // 单元测试 打印分区情况
                System.out.print("swap " + (j + 1) + " <- " + i + ", ");

                arr.swap(++j, i); // i和j+1交换, 之后j+1
            }
        }
        // 单元测试 打印分区情况
        System.out.println(";then swap " + (l) + " and " + j);

        arr.swap(l, j); // 将分区基准从l交换到j

        // 单元测试 打印分区情况
        System.out.print("ref: arr[" + j + "]  <" + arr.get(j) + ">  -->  ");
        if (j != 0)
            System.out.print(Arrays.toString(Arrays.copyOfRange(arr.getAsArray(), 0, j)));
        System.out.print("<" + arr.get(j) + ">");
        if (j + 1 < arr.length())
            System.out.print(Arrays.toString(Arrays.copyOfRange(arr.getAsArray(), j + 1, arr.length())));
        System.out.println();

        return j; //返回分区基准所在下标j
    }

    @Test
    public void testingQuickSortAndPartitionV1() {
        ArrayGeneric<Integer> arr = getRandomIntegerArray(6, 0, 9);
        System.out.println(arr);
        quickSort(arr, 0, arr.length() - 1);
        System.out.println(arr);
    }


}
